/*
 * @lc app=leetcode.cn id=139 lang=javascript
 *
 * [139] 单词拆分
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function(s, wordDict) {
    let hash=new Set(wordDict)
    let db=[true]
    for(let i=1;i<=s.length;i++){
        for(let j=0;j<i;j++){
            if(db[j]&&hash.has(s.slice(j,i))){
                db[i]=true
            }
        }
    }
    return db[s.length]?true:false
};
// @lc code=end

wordBreak("aaaaaaa",["aaaa", "aaa"])